package pers.qianyu.month_202101.date_20210121;

import org.junit.*;

import java.util.*;

/**
 * 84. 柱状图中最大的矩形
 * https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
 *
 * @author mizzle rain
 * @date 2021-01-21 16:38
 */
public class LargestRectangleArea2 {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        if (len == 0) return 0;
        int[] left = new int[len], right = new int[len];
        Deque<Integer> st = new LinkedList<>();
        for (int i = 0; i < len; i++) {
            int cur = heights[i];
            while (!st.isEmpty() && heights[st.getLast()] >= cur) st.pollLast();
            left[i] = st.isEmpty() ? -1 : st.getLast();
            st.addLast(i);
        }
        while (!st.isEmpty()) st.pollLast();
        for (int i = len - 1; i >= 0; i--) {
            int cur = heights[i];
            while (!st.isEmpty() && heights[st.getLast()] >= cur) st.pollLast();
            right[i] = st.isEmpty() ? len : st.getLast();
            st.addLast(i);
        }
        //System.out.println(Arrays.toString(left));
        //System.out.println(Arrays.toString(right));
        int res = 0;
        for (int i = 0; i < len; i++) {
            res = Math.max(res, (right[i] - left[i] - 1) * heights[i]);
        }
        return res;
    }

    @Test
    public void test1() {
        int result = new LargestRectangleArea2()
                .largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3});
        Assert.assertEquals(result, 10);
    }

    @Test
    public void test2() {
        int result = new LargestRectangleArea2()
                .largestRectangleArea(new int[]{1, 1});
        Assert.assertEquals(result, 2);
    }
}
